import java.util.Arrays;

public class LinkedListInsert {
    public static void main(String[] args) {
        //1、初始化链表 1 -> 3 -> 2 -> 5 -> 4
        ListNode node0 = new ListNode(1);  //初始化各个链表节点
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(5);
        ListNode node4 = new ListNode(4);

        node0.next = node1;  //构建节点之间的引用
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        //2、头插法验证
        ListNode newHeadNode1 = headInsert(node0, 0);
        int[] newLinkedListArray1 = LinkedListToArray.linkedListToArray(newHeadNode1);
        System.out.println(Arrays.toString(newLinkedListArray1)); //[0, 1, 3, 2, 5, 4]

        //3、任意位置插入节点验证
        ListNode newHeadNode2 = insert(3, node0, 0); //插入位置为3
        int[] newLinkedListArray2 = LinkedListToArray.linkedListToArray(newHeadNode2);
        System.out.println(Arrays.toString(newLinkedListArray2)); //[1, 3, 2, 0, 5, 4]

    }
    //插入节点 - 头插法
    // 如果当前链表为空链表，则将该节点直接作为头结点即可创建一个链表；
    // 如果当前链表不是空链表，则将要插入的节点的next指针指向原本的头节点。
    public static ListNode headInsert(ListNode headNode, int val){
        //1、创建一个要插入节点的对象
        ListNode newListNode = new ListNode(val);
        //2、判断当前链表是否 空链表
        if(headNode == null){
            headNode = newListNode;      //头节点为空 表示空链表 插入节点直接等于头节点
        }else {
            newListNode.next = headNode; //头节点非空 插入节点 指向头节点
            headNode = newListNode;
        }
        return headNode; //返回新的头节点
    }

    //插入节点 - 任意位置
    // 如果index等于0，则和头插法过程相同
    // 否则需要先创建要插入节点对象 再将当前节点指向插入位置的下一个节点 最后将前一个节点指向当前节点
    public static ListNode insert(int index, ListNode headNode, int val){
        //1、创建一个要插入节点的对象
        ListNode currentNode = new ListNode(val);
        //2、判断是否是头部插入 - 头插法
        if(index == 0){ // 插入到第0位
            //判断当前链表是否 空链表
            if(headNode == null){
                headNode = currentNode;      //头节点为空 表示空链表 插入节点直接等于头节点
            }else {
                currentNode.next = headNode; //头节点非空 插入节点 指向头节点
                headNode = currentNode;
            }
            return headNode; //返回新的头节点
        }
        //3、不是头插 - 关键是找到插入位置的前一个节点
        ListNode previousNode = headNode; //从头节点开始遍历 创建一个指向头节点的指针
        for (int i = 0; i < (index - 1); i++) {
            previousNode = previousNode.next; //用该指针找到要插入元素位置的前一个节点
        }
        currentNode.next = previousNode.next; //插入节点的next 指向要添加位置的下一个
        previousNode.next = currentNode;      //前一个节点的next 指向插入节点

        return headNode; //返回新的头节点
    }
}
